// 数组拍平的循环写法
function flat(array: any[]): number[] {
  const result: number[] = [];
  const stack: any[] = [...array];

  while (stack.length) {
    const item = stack.pop();
    if (Array.isArray(item)) {
      stack.push(...item);
    } else {
      result.push(item);
    }
  }
  return result.reverse();
}

// 深克隆
function deepCloneL(obj: any) {
  if (typeof obj !== "object" || obj === null) return obj;

  if (obj instanceof Date) return new Date(obj);
  if (obj instanceof RegExp) return new RegExp(obj);
  if (obj instanceof Set)
    return new Set([...obj].map((item) => deepCloneL(item)));
  if (obj instanceof Map)
    return new Map(
      [...obj].map(([key, value]) => [deepCloneL(key), deepCloneL(value)])
    );

  const newObj = Object.create(Reflect.getPrototypeOf(obj));
  Reflect.ownKeys(obj).forEach((key) => {
    newObj[key] = deepCloneL(obj[key]);
  });
  return newObj;
}

// 爬楼梯--动态规划
function climbStairs(n: number): number {
  if (n <= 2) return n;
  let pre = 1;
  let cur = 2;

  for (let i = 3; i <= n; i++) {
    let temp = pre;
    pre = cur;
    cur += temp;
  }

  return cur;
}

// 自实现的instanceof
function instanceofC(instance, constructor) {
  if (
    instance === null ||
    typeof constructor != "function" ||
    (typeof instance != "object" && typeof instance != "function")
  )
    return false;

  let proto = Reflect.getPrototypeOf(instance);
  let prototype = constructor.prototype;

  // 沿着链条找到匹配示例的构造函数
  while (proto) {
    if (proto === prototype) return true;
    proto = Reflect.getPrototypeOf(proto);
  }
  return false;
}

// 防抖 --回城
function debounce(fn, delay, immediate) {
  let timer;
  return function () {
    immediate && !timer && fn.apply(this, arguments);
    if (timer) {
      clearTimeout(timer);
    }
    timer = setTimeout(() => {
      fn.apply(this, arguments);
    }, delay);
  };
}

// 节流 --技能
function throttle(fn, delay) {
  let click;
  return function () {
    if (click) return;
    click = setTimeout(() => {
      fn.apply(this, arguments);
      click = null;
    }, delay);
  };
}

// 质数判断
function isPrimes(n: number) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;

  for (let i = 5; i * i <= n; i += 6) {
    if (n % i == 0 || n % (i + 2) == 0) return false;
  }
  return true;
}
// 线性筛选n以内的质数
function lineCount(n: number) {
  if (n <= 2) return [];
  const isPrimes = new Array(n).fill(true);
  const primes = [2, 3];

  function pushPrime(i) {
    if (isPrimes[i]) {
      primes.push(i);
    }
    // 遍历质数数组，将i的质数倍标记为合数
    for (let j = 0; primes[j] * i <= n; j++) {
      isPrimes[primes[j] * i] = false;
      // 如果 i 能被 primes[j] 整除，i 已是其他质数的倍数, 且该质数已记录
      if (i % primes[j] == 0) break; // 遇到最小质因数，跳出循环
    }
  }

  for (let i = 5; i <= n; i += 6) {
    pushPrime(i);
    pushPrime(i + 2);
  }
  return primes;
}

type ListNode = {
  val: number;
  next: ListNode | null;
};
// 链表去重
function deleteDuplicates2(node: ListNode | null) {
  if (!node) return null;
  const result: ListNode = { val: 0, next: null }; // 存放新链表
  let tail = result; // 尾部指针指向新链表

  while (node) {
    if (node.val !== node?.next?.val) {
      tail.next = node; // 链表添加新节点
      tail = node; // 移动尾指针
    }
    node = node?.next;
  }
  return result.next;
}

// 队列控制并发请求
function handQueue(limit: number = 6, maxRetry: number = 3) {
  let current = 0;
  const queue: { task: () => Promise<any>; retry: number }[] = [];

  function dequeue() {
    while (queue.length && current < limit) {
      current++;
      const { task, retry } = queue.shift()!;
      if (!task || retry > maxRetry) continue;

      task()
        .catch((err) => {
          console.error("Request failed:", err);
          queue.push({ task, retry: retry + 1 });
        })
        .finally(() => {
          current--;
          dequeue();
        });
    }
  }

  return (task: () => Promise<any>) => {
    queue.push({ task, retry: 0 });
    dequeue();
  };
}

// 贪心算法—— 追求舒适的逃离者
function subMax(arr: number[]) {
  let sum = 0;
  let max = arr[0];
  for (let num of arr) {
    sum += num;
    max = Math.max(max, sum);
    if (sum < 0) sum = 0;
  }
  return max;
}

// 滑动窗口—— 与时间和队友无限竞争的游戏
function slideWindow(arr: number[], k: number) {
  const res: number[] = [];
  const q: number[] = [];
  for (let i = 0; i < arr.length; i++) {
    add(i);
  }
  function add(n: number) {
    while (q.length && arr[q[q.length - 1]] <= arr[n]) {
      q.pop();
    }
    q.push(n);
    if (n >= k - 1) {
      if (n - q[0] >= k) q.shift();
      res.push(arr[q[0]]);
    }
  }
  return res;
}

interface Tree {
  val: number;
  left?: Tree;
  right?: Tree;
}
const tree = {
  val: 8,
  left: {
    val: 4,
    left: {
      val: 2,
      left: { val: 1 },
      right: { val: 3 },
    },
    right: {
      val: 6,
      left: { val: 5 },
      right: { val: 7 },
    },
  },
  right: {
    val: 12,
    left: {
      val: 10,
      left: { val: 9 },
      right: { val: 11 },
    },
    right: {
      val: 14,
      left: { val: 13 },
      right: { val: 15 },
    },
  },
};
// 深度搜索二叉树
function getPreArr(root: Tree) {
  const res: number[] = [];
  const q: Tree[] = [root];
  while (q.length) {
    const node = q.pop()!;
    res.push(node.val);
    node?.right && q.push(node.right);
    node?.left && q.push(node.left);
  }
  return res;
}
function getMidArr(root: Tree) {
  const res: number[] = [];
  const q: Tree[] = [];
  let cur: Tree | null = root;
  while (q.length || cur) {
    while (cur) {
      q.push(cur);
      cur = cur.left || null;
    }
    cur = q.pop()!;
    res.push(cur.val);
    cur = cur?.right || null;
  }
  return res;
}
function getAfterArr(root: Tree) {
  const res: number[] = [];
  const q: Tree[] = [];
  let cur: Tree | null = root;
  let pre: Tree | null = null;
  while (q.length || cur) {
    while (cur) {
      q.push(cur);
      cur = cur.left || null;
    }
    cur = q[q.length - 1];
    // 如果右子树为空或已访问，访问当前节点并出栈
    if (!cur.right || pre == cur.right) {
      res.push(cur.val);
      pre = q.pop()!;
      cur = null;
    } else {
      cur = cur.right;
    }
  }

  return res;
}
// 由前中序数组构建二叉树
function buildTree(pre: number[], mid: number[]) {
  if (!pre.length || !mid.length) return;
  const node: Tree = { val: pre[0] };
  const index = mid.indexOf(node.val);
  node.left = buildTree(pre.slice(1, index + 1), mid.slice(0, index));
  node.right = buildTree(pre.slice(index + 1), mid.slice(index + 1));
  return node;
}
